zkp update
$$ \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ps#1{\delim\{{#1}\}} \gdef\F{\mathbb F} \gdef\set#1{\mathcal #1} \gdef\mat#1{\mathrm #1} \gdef\vec#1{\bm #1} $$
Customizable Constraint System (CCS)
In STW23 a CCS is a set of sets of matrices $\set S$ such that a witness $\vec w$ satisfies
$$ \sum_{\set T ∈ \set S}\ \bigodot_{M ∈ \set T}\ M ⋅ \vec w = \vec 0 $$
where $\bigodot$ is the Hadamard product.
A R1CS constraint is a triplet of matrices $(A,B,C)$ such that a witness $\vec w$ satisfies $\p{A⋅\vec w} ∘ \p{B⋅\vec w} = C⋅\vec w$. A R1CS becomes $\ps{\ps{A,B},\ps{-C}}$. For transformation of Plonkish and AIR constraints see STW23.
Note. CCS is closed under conjunction. Given two CCS constraints $\set S_1$ and $\set S_2$ with matrices of size $m_1×n$ and $m_2×n$ respectively. Convert all matrices to $\p{m_1 + m_2} × n$ as $\begin{bmatrix}M \\ 0\end{bmatrix}$ and $\begin{bmatrix}0 \\ M\end{bmatrix}$ respectively. The conjoined CSS is now the union.
Q. The degree of the CCS is $\max_{\set T ∈ \set S} \delim\vert{\set T}\vert$ and the rank is the number of rows in the matrices. Can we reduce the degree by increasing the rank? For example we can reduce $\ps{\ps{A, B}, \ps{C}}$ to $\ps{\ps{D, D}, \ps{E}}$ at doubling rank.
CCS+ extends this with a lookup argument. In addition to the above there is a set of indices $\set I$ and a set of field elements $\set T$. The witness additional satisfies
$$ \operatornamewithlimits{\large \forall}_{i∈\set I}\ w_i ∈ \set T $$
Q. How do we conjoin table lookup arguments?
Sum-check
Introduced in LFKN92. Given multivariate polynomial $G ∈ \F[X_1,…,X_n]$ and domain $\set B = \set B_1 × ⋯ × \set B_n$, $\set B_i \subseteq \F$. Typically $\set B = \ps{0,1}^n$. We want to proof
$$ h = \sum_{\vec x ∈ \set B} G\p{\vec x} $$
The prover commits to $G$ such that the verifier has oracle access to evaluate $G(\vec x)$ for $\vec x ∈ \F^n$.
Prover sends $G_1 ∈ \F[X]$
$$ G_1(X) = \sum_{\vec x ∈ \set B_2×⋯×\set B_n} G\p{X, \vec x} $$
verifier checks
$$ h = \sum_{x ∈ \set B_1} G_1\p{x} $$
verifier sends random $r ∈ \F$.
prover sends
$$ G_2(X) = \sum_{\vec x ∈ \set B_3×⋯×\set B_n} G\p{r, X, \vec x} $$
verifier checks that degree of $G_2$ equals degree of $X_2$ in $G$ and
$$ G_1(r) = \sum_{x ∈ \set B_2} G_2\p{x} $$
repeat until prover sends
$$ G_n(X) = G\p{\vec r, X} $$
. Verifier takes a random $r ∈ \F$ and checks
$$ G_n(r) = G(\vec r) $$
using any means to compute $G\p{\vec r}$.
See Justin Thaler's notes on Sum-Check: https://people.cs.georgetown.edu/jthaler/sumcheck.pdf
Small field optimization https://people.cs.georgetown.edu/jthaler/small-sumcheck.pdf
https://zkproof.org/2020/03/16/sum-checkprotocol/
GKR
https://people.cs.georgetown.edu/jthaler/gkrnotes.pdf https://people.cs.georgetown.edu/jthaler/GKRNote.pdf
